iT邦幫忙

2024 iThome 鐵人賽

DAY 23
0

2024/09/26 Leetcode Daily Problem

2707. Extra Characters in a String
難度: 中等

題意

給定一字串s及一字串陣列dictionary
可以將s分割成任意數量的非交疊子字串;求不在字典dictionary中的字串,字元最少有幾個。

範例1
Input: s = "leetscode", dictionary = ["leet","code","leetcode"]
Output: 1
s可分割成"leet"+"s"+"code",多餘的"s"共有1個字元,故回傳1。

範例2
Input: s = "sayhelloworld", dictionary = ["hello","world"]
Output: 3
s可分割成"say"+"hello"+"world",多餘的"say"共有3個字元,故回傳3。

思路

動態規劃問題: 問題可以拆解為子問題,而問題可以由子問題的最佳解組合而成。通常會用到填表法來求。

s長度為n。
設定長度為n+1的整數陣列dpdp[i]代表s在索引值i ~ n-1的最佳解。
由索引值n - 1到0求解,方便切割字串去dictionary查找,如果反過來求dp感覺很麻煩~
dp[i]可以是以下的子問題最優解得到:

  1. s[i]不選,則s[i]是一個多餘的字元,子問題的解為s[i + 1] + 1

範例: Input: s = "leetscode", dictionary = ["leet","code","leetcode"]
當i = 4時,s[i] = 's',若不選s[4],則此子問題為s[5] + 1。
又s[5]開頭剛好是"code",s[5] = 1,s[4] = s[5] + 1。

  1. s[i]選,則s[i]是dictionary中某個字串的開頭。故從遍歷所有從i開頭的字串,去檢查是否存在於dictionary中。若存在一個長度為len的字串,則此問題的可能解為s[i + len]。

實作

class Solution
{
public:
    int minExtraChar(string s, vector<string> &dictionary)
    {
        // Build hash map for O(1) search
        unordered_set<string> us(dictionary.begin(), dictionary.end());

        int n = (int)s.length();
        // dp[i] is the best solution for substring s[i : n - 1]
        vector<int> dp(n + 1, 0); // Initialize to 0

        // Build dp from tail
        for (int i = n - 1; i >= 0; i--)
        {
            // One solution: s[i] is a extra character
            int curr_min = dp[i + 1] + 1;
            
            // Other solutions: s[i] is a start of substring
            // Traverse all substring start from index i
            for (int len = 1; (i + len) <= n; len++)
            {
                // Find substring in dictionary
                if (us.find(s.substr(i, len)) != us.end())
                {
                    curr_min = min(curr_min, dp[i + len]);
                }
            }
            
            // Update current solution
            dp[i] = curr_min;
        }

        return dp[0];
    }
};

分析

s長度為N,dictionary有M個字串。
時間複雜度:O(M + N ^ 2),建立hash table O(M),遍歷所有子字串O(N ^ 2)
空間複雜度:O(M + N),Hash table + dp陣列

結果

Accepted
2028/2028 cases passed (125 ms)
Your runtime beats 56.76 % of cpp submissions
Your memory usage beats 52.7 % of cpp submissions (86.8 MB)

這題的測資也太多了吧~~ 應該是週賽的題目才會有如此誇張多的測資。

總結

Time Submitted Status Runtime Memory Language
09/23/2024 23:02 Accepted 125 ms 86.8 MB cpp

上一篇
[9/22] 1~n字典序的第k個
下一篇
[9/24] 兩整數陣列中最長的相同前綴長度
系列文
菜就多練,不會就多刷31
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言